/*
 * @lc app=leetcode id=494 lang=cpp
 *
 * [494] Target Sum
 */

// @lc code=start
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int s = 0;
        for (auto n : nums) {
            s+= n;
        }
        if (s < target || (s + target) % 2 != 0 ) {
            return 0;
        }
        int t = ( s+ target) >> 1;
        vector<int> dp(t + 1, 0);
        dp[0] = 1;
        for (auto n : nums) {
            for (int i = t ; i >= n ; --i) {
                dp[i] += dp[i-n];
            }
        }
        return dp[t];


    }
};
// @lc code=end

